# 折半查找算法

def main():
    #       0, 1, 2  3   4   5   6
    ints = [6, 8, 9, 10, 12, 22, 68]
    print("result:", search(ints, 6, 0, len(ints) - 1))

def search(arr, num, L, R):
    # middle = len(arr)//2
    if num<arr[L] or num>arr[R]:
        print("no found.")
        return -1
    middle = (R - L)//2+L
    print(f"middle={middle}")
    # if L>R:
    #     print("L>R")
    #     return
    if num < arr[middle]:
        # 查左边
        print(f"search left: l={L},r={middle-1}")
        search(arr,num,L,middle-1)
    elif num > arr[middle]:
        # 查右边
        print(f"search right: l={middle+1},r={R}")
        search(arr,num,middle+1,R)
    else:
        print(f"found,  index = {middle}")
        return middle


if __name__ == '__main__':
    main()
